import java.util.Arrays;

public class Solution {
    /**
     * 上课期间代码（数据结构）
     * */
    public static void main(String[] args) {
        Solution test = new Solution();

        String s = "abcabcabcabc";
        System.out.println(test.longestPalindromeSubseq(s));
    }

    public int longestPalindromeSubseq1(String s) {
        /**
         * 最长回文子序列
         *  状态表示：
         *      dpp[i]表示以i下标为结尾的所有子序列中，最长回文子序列的长度
         *  状态转移方程：
         *      // j为从前遍历找相同值的下标
         *      if(s.charAt(i) == s.charAt(j)) {
         *          dpp[i] = 2;
         *          int diff = i - j;
         *          for(int k = diff; k >= 0; k--) {
         *              while(j + diff <= i) {
         *                  if(dp[j][j + diff]) {
         *                      dpp[i] += diff + 1;
         *                      break;
         *                  }
         *              }
         *              if(dpp[i] > 2) break;
         *          }
         *      }
         *  初始化：
         *      默认最差情况，就是本身，也就是长度为1
         *  填表顺序：
         *      从左到右
         *  返回值：
         *      返回dpp表中的最大值
         * */
        // 1 预处理
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for(int i = n-1; i >= 0; i--) {
            for(int j = i; j < n; j++) {
                if(s.charAt(i) == s.charAt(j)) {
                    if(i+1 >= j || dp[i+1][j-1]) {
                        dp[i][j] = true;
                    }
                }
            }
        }
        // 2 创建dp表
        int[] dpp = new int[n];
        // 3 初始化
        Arrays.fill(dpp, 1);
        // 4 填表
        int maxLength = 1;
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < i; j++) {
                // -若是从头到尾找到一个一样的值，则继续找中间值
                if(s.charAt(i) == s.charAt(j)) {
                    // -既然找到一样的值，那么现在长度就为2，更新值
                    dpp[i] = 2;
                    // -遍历中间值，使用缩小移动窗口的方式，从大到小进行枚举（端点处不算）
                    int diff = i - j - 2;
                    for(int k = diff; k >= 0; k--) {
                        int tempStart = j+1;
                        while(tempStart + k < i) {
                            if(dp[tempStart][tempStart + k]) {
                                dpp[i] += k + 1;
                                break;
                            }
                            tempStart ++;
                        }
                        if(dpp[i] > 2) break;
                   }
                    // -更新长度
                    if(dpp[i] > maxLength) maxLength = dpp[i];
                    break;
               }
            }
        }
        // 5 返回值
        return maxLength;
    }

    public int longestPalindromeSubseq(String s) {
        /**
         * 最长回文子序列
         * 解题思路：
         *  刚才思路错了，此处说的是回文子序列，也就是说，中间的回文子串可能也是子序列，此时之前的那种方式就无法使用了
         * */
        return 0;
    }
}
